package 寻找存在的路径;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author: AirMan
 * @date: 2025/6/6 10:44
 * @description:
 * 题目描述
 * 给定一个包含 n 个节点的无向图中，节点编号从 1 到 n （含 1 和 n ）。
 * 你的任务是判断是否有一条从节点 source 出发到节点 destination 的路径存在。
 * 输入描述
 * 第一行包含两个正整数 N 和 M，N 代表节点的个数，M 代表边的个数。
 * 后续 M 行，每行两个正整数 s 和 t，代表从节点 s 与节点 t 之间有一条边。
 * 最后一行包含两个正整数，代表起始节点 source 和目标节点 destination。
 * 输出描述
 * 输出一个整数，代表是否存在从节点 source 到节点 destination 的路径。如果存在，输出 1；否则，输出 0。
 * 输入示例
 */
public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        union_find_set unionSet = new union_find_set(n+1);

        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            unionSet.union(u, v);
        }
        System.out.println(Arrays.toString(unionSet.father));
        int source = sc.nextInt();
        int destination = sc.nextInt();
        if (unionSet.find(source) == unionSet.find(destination)){
            System.out.println(1);
        }else{
            System.out.println(0);
        }
    }

}


class union_find_set {
    public static int[] father;
    public static int[] rank;

    public union_find_set(int n) {
        father = new int[n];
        for (int i = 0; i < n; i++) {
            father[i] = i;
        }
        rank = new int[n];
    }

    public int find(int u) {
        // 路径压缩
        if (u != father[u]) {
            u = find(father[u]);
        }
        return father[u];
    }

    public void union(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) return;
        // 根据秩进行连接
        if (rank[u] < rank[v]) {
            father[u] = v;
        } else if (rank[u] > rank[v]) {
            father[v] = u;
        } else {
            father[v] = u;
            rank[u] += 1;
        }
    }
}

